This invention concerns machines for recognizing and extracting information from patterns of data. More specifically this invention concerns machines for determining the angle and orientation of lines in a two dimensional scene by use of Hadamard transform coefficients.
Machines for extracting information from large sets of data have become increasingly important in the automation arts. These machines are capable of recognizing information contained in the features of the data set and of rejecting noise or background information. Pattern recognition machinery of this type presently finds use in optical character readers, guidance and inspection systems, and many other sectors of that art. Often the data set is in the form of video scene information which may, for example, be derived from a television camera pickup or from a radar or sonar scanning system.
Early pattern recognition machines operated by comparing small sectors of scene data with suitable masks representing the desired pattern information. More useful information can be extracted from such scene data, however, if the pattern information produced is of a more fundamental nature. For example, if the position and angle of a line or edge in the scene is known, it is possible, by the application of relatively simple data manipulation, to follow and trace the path of that line or edge.
It is well known that any function having finite energy may be expressed as the sum of a series of orthogonal functions. In 1923 Joseph L. Walsh devised a complete set of orthogonal functions, now known as Walsh functions, which are especially useful for the representation of binary waveforms. Walsh functions, which are denoted by the expression EQU wal (s,t),
are binary functions having values of +1 and -1 in the unit interval. The sequency, s, of a Walsh function is defined herein as the number of times the value of that function changes sign within the unit interval (the term "sequency" is also used in the literature to denote one-half the number of sign changes in the unit interval). The sequency of a Walsh function may be seen to be somewhat analogous to the frequency of the more common sine or cosine functions.
A series of Walsh functions may be expressed in a matrix, known as a Hadamard matrix, in which elements are either +1 or -1 and in which the respective row vectors and the respective column vectors are mutually orthogonal. The values of the elements in a row or column of a Hadamard matrix represent the values of a Walsh function over sequential segments of the unit interval. Successive examination of the rows or columns of a Hadamard matrix yields a set of Walsh functions which are known as Hadamard functions denoted EQU H(n,t).
The natural order n, of a Hadamard function denotes the order in which that function is generated from a Hadamard matrix in the manner described above which is not the sequency order. Further discussion of the properties of Hadamard and Walsh functions and of algorithms for generating Hadamard matrices may be found in H. F. Harmuth, "Transmission of Information by Orthogonal Functions", Second Edition, Springer-Verlag, 1972.
The Walsh transform vector w.sub.a of a binary function vector f may be expressed in matrix notation as: EQU w.sub.a = [ wal ] f.sub.a (1)
where [ wal ] is a matrix whose rows are sequency ordered Walsh functions. The order of a Walsh transform, as defined herein, means the number of dimensions in the vector w.sub.a which may be seen to equal the rank of the matrix [ wal ]. A Hadamard transform is a Walsh transform wherein the matrix [wal] is a Hadamard matrix.
Machines for generating the value of Walsh functions are well known in the computing arts. For example, U.S. Pat. No. 3,701,143 to Nacht, U.S. Pat. No. 3,795,864 to Fullton, Jr., and U.S. Pat. No. 3,742,201 to Groginski, describes such machine. A copending U.S. Patent Application by Ruben E. Joynson and Joseph L. Mundy, Ser. No. 563,820 of common assignee, describes a fast Hadamard transform generating machine which yields serial streams of Hadamard transform coefficients in sequency order.
Two dimensional Hadamard transforms may be used to represent variations in brightness over a two dimensional video scene. Further information on the generation and use of two dimensional Hadamard transforms in this application may be found in the abovementioned Harmuth reference. Our copending patent application, referenced above, describes a machine for generating a matrix of two dimensional Hadamard transform coefficients from video information.